package ch5.part4;

/**
 * 求最大公约数的算法最优解
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class MaximumCommonDivisor {

    private static int TWO = 2;

    /**
     * 暴力枚举法
     * 时间复杂度：O(n) = min(a,b)
     *
     * @param a 正整数a
     * @param b 正整数b
     * @return 最大公约数
     */
    private static int calcV1(int a, int b) {
        int max = a > b ? a : b;
        int min = a < b ? a : b;
        if (max % min == 0) {
            return min;
        }
        for (int i = min / TWO; i > 1; i--) {
            if (min % i == 0 && max % i == 0) {
                return i;
            }
        }
        return 1;
    }

    /**
     * 辗转相除法，取模运算行交叉
     * 时间复杂度：O(n) ≈ log(max(a,b))
     *
     * @param a 正整数a
     * @param b 正整数b
     * @return 最大公约数
     */
    private static int calcV2(int a, int b) {
        int max = a > b ? a : b;
        int min = a < b ? a : b;
        if (max % min == 0) {
            return min;
        }
        return calcV2(max % min, min);
    }

    /**
     * 更相减损法
     * 时间复杂度：O(n) ≈ log(max(a,b))
     * 最坏时间复杂度：O(n) = max(a,b)
     *
     * @param a 正整数a
     * @param b 正整数b
     * @return 最大公约数
     */
    private static int calcV3(int a, int b) {
        if (a == b) {
            return a;
        }
        int max = a > b ? a : b;
        int min = a < b ? a : b;
        return calcV3(min, max - min);
    }

    /**
     * 更相减损法与移位相结合
     * 时间复杂度：O(n) = log(max(a,b))
     *
     * @param a 正整数a
     * @param b 正整数b
     * @return 最大公约数
     */
    private static int calcV4(int a, int b) {
        if (a == b) {
            return a;
        }
        if ((a & 1) == 0 && (b & 1) == 0) {
            return calcV4(a >> 1, b >> 1) << 1;
        } else if ((a & 1) == 0 && (b & 1) == 1) {
            return calcV4(a >> 1, b);
        } else if ((a & 1) == 1 && (b & 1) == 0) {
            return calcV4(a, b >> 1);
        } else {
            int max = a > b ? a : b;
            int min = a < b ? a : b;
            return calcV4(min, max - min);
        }
    }

    public static void main(String[] args) {
        System.out.println(calcV1(100, 80));
        System.out.println(calcV2(25, 5));
        System.out.println(calcV3(27, 18));
        System.out.println(calcV4(52, 26));

        System.out.println(calcV1(10001, 10000));
        System.out.println(calcV2(10001, 10000));
        System.out.println(calcV3(10001, 10000));
        System.out.println(calcV4(10001, 10000));
    }

}
